package solution;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.file.NotLinkException;
import java.util.*;
import java.util.stream.Collectors;

public  class Solution {
    /*
    最长连续子序列
     */
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        HashSet<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            set.add(num);
        }
        int max = 0;
        for (int num : set) {
            //把所有数组元素存储到Set中去重，从头开始判断起点元素，如果是起点，往后累加遍历
            if(!set.contains(num - 1)) {
                int curLen = 1;
                while(set.contains(num + 1)) {
                    curLen ++;
                    num ++;
                }
                max = Math.max(max, curLen);
            }
        }
        return max;
    }

    /*
    字母异位词
    输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
    输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        return new ArrayList<>(Arrays.stream(strs)
                .collect(Collectors.groupingBy(str -> {
                    char[] array = str.toCharArray();
                    Arrays.sort(array);
                    return new String(array);
                })).values());
    }

    /*
    移动零
    输入: nums = [0,1,0,3,12]
    输出: [1,3,12,0,0]
     */
    public void moveZeroes(int[] nums) {
        //参考快速排序思想，把0作为枢轴元素，所有非零元全部移动到左边，零交换到右边
        //i指向未处理序列的最左边，j指向处理好的序列的左右边
        if(nums == null) return;
        int j = 0, temp;
        for(int i = 0; i < nums.length;i++) {
            if(nums[i] != 0) {
                temp = nums[i];
                nums[i] = nums[j];
                nums[j++] = temp;
            }
        }
    }

    /*
    三数之和
    输入：nums = [-1,0,1,2,-1,-4]
    输出：[[-1,-1,2],[-1,0,1]]
    先排序，如果i == i + 1 说明一定会有相同的情况出现直接跳过
              i + L < 0  说明L指针需要向后移动
              i + L > 0  说明R指针需要向前移动

     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        //排序
        Arrays.sort(nums);
        //双指针
        int len = nums.length;
        if (len < 3) return lists;
        for (int i = 0; i < len; ++i) {
            if (nums[i] > 0) return lists;
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int L = i + 1, R = len - 1;
            while(L < R) {
                int tmp = nums[i] + nums[L]+ nums[R];
                if(tmp == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[L]);
                    list.add(nums[R]);
                    lists.add(list);
                    while(L < R && nums[L + 1] == nums[L]) ++L;
                    while(L < R && nums[R - 1] == nums[R]) --R;
                    ++L;
                    --R;
                } else if(tmp < 0) {
                    ++L;
                } else {
                    --R;
                }

            }
        }
        return lists;
    }

    /**
     * 盛水最多的容器
     * 输入：[1,8,6,2,5,4,8,3,7]
     * 输出：49
     * 解释：输入数组 [1,8,6,2,5,4,8,3,7]代表水槽的高度。在此情况下，容器能够容纳水的最大值为 49。
     * 左右指针分别标记左右连个水槽
     * 水槽收缩可能会得到更大面积的情况----收缩后的水槽更高
     * 水槽收缩一定不会得到更大面积的情况--收缩后的水槽更低
     * 策略：每次选择高度小的一条边向内收缩找更高的边，与当前面积进行比较保留更大的
     */
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1, res = 0;
        while (i < j) {
            res = height[i] < height[j] ?
                    Math.max(res, height[i++] * height[j] * (j - i)):
                    Math.max(res, height[j--] * height[i] * (j - i));
        }
        return res;
    }

    /**
     * 接雨水：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     * 输入：height = [4,2,0,3,2,5]
     * 输出：9
     * 思路：查每一列能存储的雨水
     * 第一列和最后一列不能存储雨水、从1-----height.length-1,找出当前列两边最高的边，两边之间较低的决定当前列能存储多少雨水
     */
    public int trap1(int[] height) {
        int sum = 0, max_left = 0, max_right = 0;
        // 最边上的两段不用考虑
        for (int i = 1; i < height.length; i++) {
            // 找出左边的最高
            for (int j = i - 1; j >= 0; j--) {
                if (height[j] > max_left)   max_left = height[j];
            }
            // 找到有百年的最高
            for (int j = i + 1; j < height.length; j++) {
                if(height[j] > max_right) max_right = height[j];
            }
            // 挑出两段中更低的那一段
            int min = Math.min(max_left, max_right);
            if (min > height[i]) {
                sum += min - height[i];
            }
        }
        return sum;
    }

    public int trap2(int[] height) {
        int sum = 0;
        int[] max_left = new int[height.length];
        int[] max_right = new int[height.length];
        // 当前列的max_left = Math.max(max_left[i - 1], height[i - 1])
        for (int i = 1; i < height.length; i++)
             max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
        for (int i = height.length - 2; i >= 0; i--)
            max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
        for (int i = 1; i < height.length; i++) {
            int min = Math.min(max_left[i], max_right[i]);
            if (min > height[i])
                sum += min - height[i];
        }
        return sum;
    }

    /**
     * 无重复字符的最长字串：给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
     * 输入: s = "abcabcbb"
     * 输出: 3
     * 思路： 滑动窗口，从做指针开始，一直向后寻找当前窗口中不存在的字符并插入，去重考虑HashSet
     * */
    public int lengthOfLongestSubstring(String s) {
        HashSet<Character> set = new HashSet<>();
        int n = s.length();
        // 右指针初始值为-1，表示刚开始右指针在字符串的左边界还没有开始移动
        int rk = -1, ans = 0;
        for ( int i = 0; i < n; i++) {
            if (i != 0) {
                // 左指针向右移动一格，并移除窗口中做左边的元素
                set.remove(s.charAt(i - 1));
            }
            // 右指针持续向后寻找窗口中不存在的元素并加入窗口
            while (rk + 1 < n && !set.contains(s.charAt(rk + 1))) {
                set.add(s.charAt(rk + 1));
                rk++;
            }
            // 更新ans的值
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }

    /**
     * 找到字符串中所有字母异位词：给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
     * 输入: s = "cbaebabacd", p = "abc"
     * 输出: [0,6]
     * 思路：滑动窗口，在 s 串中维护一个大小跟 p 串一样的数组窗口，用来记录每个字符的出现次数，如果字符出现次数相同说明是异位词
     */
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        // 如果 s 串的长度小于 p 串的长度，则无法找出异位词
        if (sLen < pLen)
            return new ArrayList<>();
        ArrayList<Integer> ans = new ArrayList<>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; i ++) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }
        if (Arrays.equals(sCount, pCount))
            ans.add(0);
        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s.charAt(i) - 'a'];    // 减去窗口的第一个字符
            ++sCount[s.charAt(i + pLen) - 'a'];// 窗口后移
            if (Arrays.equals(sCount, pCount))
                ans.add(i - pLen + 1);
        }
        return ans;
    }

    /**
     * 和为 k 的子串：给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的<连续非空序列>
     * 输入：nums = [1,2,3], k = 3
     * 输出：2
     * 思路一：枚举----end为当前扫面到的元素，从 end 开始从后往前累加，找出 sum == k 的情况并计数，没有则不计数，如果累加和超出 k 显然也无法计数
     * 时间复杂度 O(n^2)
     */
    public int subarraySum1(int[] nums, int k) {
        int count = 0;
        for (int end = 0; end < nums.length; ++end) {
            int sum = 0;
            for (int start = end; start >= 0; --start) {
                sum += nums[start];
                if (sum == k) ++count;
            }
        }
        return count;
    }

    /**
     * 滑动窗口最大值：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
     *             返回 滑动窗口中的最大值 。
     * 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
     * 输出：[3,3,5,5,6,7]
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 滑动窗口数量为 nums.length - k + 1
        int[] ans = new int[nums.length - k + 1];
        // 创建一个双端队列用来存储数组元素的索引
        Deque<Integer> queue = new LinkedList<>();
        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            // 当队列不为空且当前的队尾下标值小于当前数组值时
            // 不断移除队尾元素， 保证队列中的元素索引对应的数组元素单调递减
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
                queue.pollLast();
            }
            // 将当前元素索引加入队尾
            queue.offerLast(i);
            // 当前滑动窗口的范围是 [i - k + 1, i]
            if (queue.peek() < i - k + 1) {
                // 如果队首元素索引位置小于当前窗口的左边界时，移除该元素
                queue.poll();
            }
            // 当滑动窗口的大小达到 k 时，记录当前滑动窗口的最大值
            if (i + 1 >= k) {
                // 队首元素索引对应的数组值就是当前窗口中的最大值
                ans[i - k + 1] = nums[queue.peek()];
            }
        }
        return ans;
    }

    /**
     * 相交链表：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
     * 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
     * 输出：Intersected at '8'
     * 思路一：哈希集合  ----> 首先遍历链表A，将其全部加入Set集合中（Set不允许重复），再开始遍历链表B，并判断当前扫描到的节点是否在Set中，存在则返回该节点
     * 时间复杂度： O(m + n)
     */
    public static class ListNode {
        int value;
        ListNode next;
        ListNode() {}
        ListNode(int x) {
            this.value = x;
        }
        ListNode(int x, ListNode next) {
            this.value = x;
            this.next = next;
        }
    }
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<>();
        // 创建ListNode类型的扫描器，便于返回单个节点
        ListNode temp = headA;
        // 将链表A中的所有元素全部添加到 set 集合中
        while (temp != null) {
            visited.add(temp);
            temp = temp.next;
        }
        // 顺序扫描链表 B ，如果 set 集合中存在当前扫描到的节点，直接返回；不存在继续向后扫描并加入 set 集合中
        temp = headB;
        while (temp != null) {
            if (visited.contains(temp)) return temp;
            temp = temp.next;
        }
        return null;
    }

    /**
     * 思路二：双指针  ---->  创建两个指针 pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        // 如果两个链表存在任何一个为空则不可能相交
        if (headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

    /**
     * 反转链表 ：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     * 输入：head = [1,2,3,4,5]
     * 输出：[5,4,3,2,1]
     * 思路 ：遍历链表时，将当前扫描到的节点的 next 切换为他的前驱节点
     * 时间复杂度 ： O(n)
     */
    public ListNode reverseList(ListNode head) {
        // prev 置空, 扫描器置为头节点
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    /**
     * 回文链表 ： 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
     * 输入：head = [1,2,2,1]
     * 输出：true
     * 思路 ： 先把链表值存入数组，再判断是不是回文数组  front  back
     * 时间复杂度 ： O(n^2)
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null) return false;
        ArrayList<Integer> arr = new ArrayList<>();
        // 创建 ListNode 类型的扫描器
        ListNode curr = head;
        // 扫描器不空则向后遍历并将节点数据域存入 arr
        while (curr != null) {
            arr.add(curr.value);
            curr = curr.next;
        }
        int front = 0, back = arr.size() - 1;
        while (front < back) {
            if (arr.get(front) != arr.get(back)) return false;
            front ++;
            back --;
        }
        return true;
    }

    /**
     * 环形链表 ： 给你一个链表的头节点 head ，判断链表中是否有环。
     * 输入：head = [3,2,0,-4], pos = 1
     * 输出：true
     * 思路 ：哈希表存储所有已经访问过的节点
     * 时间复杂度 ： O(n)
     */
    public boolean hasCycle1 (ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        while (head != null) {
            if (!visited.add(head)) return true;
            head = head.next;
        }
        return false;
    }

    /**
     * 思路二 ： 快慢指针，定义 slow 和 fast 指针，slow 每次向后一位，fast 每次向后两位，while(fast != slow)
     * 时间复杂度 ： O(n)
     */
    public boolean hasCycle2 (ListNode head) {
        ListNode slow = head, fast = head;
        if (fast == null || slow == null) return false;
        do {
            if (fast == null || fast.next == null) return false;
            slow = slow.next;
            fast = fast.next.next;
        } while (slow != fast);
        return true;
    }

    /**
     * 合并两个有序链表 ：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     * 输入：l1 = [1,2,4], l2 = [1,3,4]
     * 输出：[1,1,2,3,4,4]
     * 思路 ： 递归求解  比较两个链表扫描器，将较小的保留，并递归求解剩余的和另一个链表
     * 时间复杂度 : O(n + m)
     */
    public ListNode mergeTwoList (ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        } else if(list1.value < list2.value) {
            list1.next = mergeTwoList(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoList(list1, list2.next);
            return list2;
        }
    }

    /**
     * 环形链表 ： 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     * 输入：head = [3,2,0,-4], pos = 1
     * 输出：返回索引为 1 的链表节点
     * 思路 ： 哈希表  遍历链表并存入哈希表，如果发现哈希表中存在该节点说明该节点是入环的第一个节点
     */
    public ListNode detectCycle1(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        ListNode ans = head;
        while (ans != null) {
            if (visited.contains(ans)) {
                return ans;
            } else {
                visited.add(ans);
            }
            ans = ans.next;
        }
        return null;
    }
    /**
     * 思路二 : 快慢指针 ---->  slow每次向后走一位， fast 每次向后走两位  直到两个指针相遇说明找到了环，此时为了契合题目要求，需再创建一个ListNode
     * 时间复杂度 ： O(n)
     */
    public ListNode detectCycle2(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ans = head;
                while (ans != slow) {
                    ans = ans.next;
                    slow = slow.next;
                }
                return ans;
            }
        }
        return null;
    }

    /**
     * 两数相加 ： 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
     * 请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     * 思路 ：
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0); // 哑节点标记链表头
        ListNode current = dummyHead;        // 扫描器
        int carry = 0;                       // 进位值

        while (l1 != null || l2 != null || carry != 0) { // 完全遍历条件
            int val1 = (l1 != null) ? l1.value : 0; // 安全取值
            int val2 = (l2 != null) ? l2.value : 0;

            int sum = val1 + val2 + carry;      // 两数位求和 + 进位
            carry = sum / 10;                   // 更新进位
            current.next = new ListNode(sum % 10); // 创建新节点

            // 指针后移
            current = current.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        return dummyHead.next; // 返回有效头节点
    }

    /**
     * 删除链表的第 n 个节点 ： 给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     * 思路 : 快慢指针 ,保持两个指针之间相差 n 个节点向后遍历
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建哑节点标记返回链表的位置，防止断链
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        // 将first 先向后遍历n 个位置
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }

    /**
     * 两两交换链表中的节点 ： 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
     * 思路 ：递归
     */
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        return newHead;
    }

    /**
     * 随机链表的复制 ： 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。实现深拷贝
     * 思路 ：回溯 + hashMap
     * 利用回溯的方式，让每个节点的拷贝操作相互独立。对于当前节点，我们首先要进行拷贝，然后我们进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝，
     * 拷贝完成后将创建的新节点的指针返回，即可完成当前节点的两指针的赋值。
     */
    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    // 缓存已经拷贝过的节点
    Map<Node, Node> cacheNode = new HashMap<>();
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        // 如果当前节点没有被拷贝过，则进行拷贝
        if (!cacheNode.containsKey(head)) {
            Node headNew = new Node(head.val);
            cacheNode.put(head, headNew);
            headNew.next = copyRandomList(head.next);
            headNew.random = copyRandomList(head.random);
        }
        return cacheNode.get(head);
    }

    /**
     * 排序链表 ： 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
     * 思路 ：自顶向下的归并排序
     */
    public ListNode sortList(ListNode head) {
        // 链表为空直接返回
        if (head == null) return null;
        return sortList(head, null);
    }
    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) return head;
        // 如果子表只有一个节点，则直接返回head
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        // 创建快慢指针用来找到mid ，其中快指针每次向后移动两个位置
        ListNode slow = head, fast = head;
        while (fast != tail) {
            fast = fast.next;
            slow = slow.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = merge(list1, list2);
        return sorted;
    }
    public ListNode merge(ListNode head1, ListNode head2) {
       // 创建哑节点用来标记返回链表防止断链
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.value < temp2.value) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }

    /**
     * LRU缓存 ： 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
     * 思路 ：
     */
    class LRUCache {
        // 自定义双向链表
        class DLinkedNode {
            int key;
            int value;
            DLinkedNode prev;
            DLinkedNode next;
            public DLinkedNode() {}
            public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
        }
        // 缓存数据的键 到  其在双向链表中的位置
        private Map<Integer, DLinkedNode> cache = new HashMap<>();

        private int size;

        private int capacity;

        private DLinkedNode head, tail;

        public LRUCache(int capacity) {
            this.size = 0;
            this.capacity = capacity;
            // 使用伪头节点和伪为节点
            head = new DLinkedNode();
            tail = new DLinkedNode();
            head.next = tail;
            tail.prev = head;
        }

        public int get(int key) {
            DLinkedNode node = cache.get(key);
            if (node == null) return -1;
            // 如果key存在， 先通过hash表定位，再移动到头部
            moveToHead(node);
            return node.value;
        }

        public void put(int key, int value) {
            DLinkedNode node = cache.get(key);
            if (node == null) {
                // 如果key 不存在，创建一个信介蒂纳
                DLinkedNode newNode = new DLinkedNode(key, value);
                // 添加进哈希表
                cache.put(key, newNode);
                // 添加到双向链表的头部
                addToHead(newNode);
                ++size;
                if (size > capacity) {
                    // 如果超出容量则删除双向链表的尾部节点
                    DLinkedNode tail = removeTail();
                    // 删除哈希表中的对应项
                    cache.remove(tail.key);
                    --size;
                }
            } else {
                // 如果key 存在，先通过哈希表定位， 再修改value ，并移动到头部
                node.value = value;
                moveToHead(node);
            }
        }

        private void addToHead(DLinkedNode node) {
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }

        private void removeNode(DLinkedNode node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        private void moveToHead(DLinkedNode node) {
            removeNode(node);
            addToHead(node);
        }

        private DLinkedNode removeTail() {
            DLinkedNode res = tail.prev;
            removeNode(res);
            return res;
        }
    }




    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 二 叉树的中序遍历
     * 输入：root = [1,null,2,3]
     * 输出：[1,3,2]
     * 思路 : 左  根   右
     */
    public List<Integer> inorderTraversal (TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        inorder(root, ans);
        return ans;
    }
    public void inorder (TreeNode root, List<Integer> ans) {
        if (root == null) return;
        inorder(root.left, ans);
        ans.add(root.val);
        inorder(root.right, ans);
    }

    /**
     * 二 叉树的最大深度 ： 二 叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
     * 输入：root = [3,9,20,null,null,15,7]
     * 输出：3
     * 思路 ： 递归
     * 时间复杂度 ： O(n)
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

    /**
     * 反转二叉树 ： 给你一棵二 叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
     * 输入：root = [4,2,7,1,3,6,9]
     * 输出：[4,7,2,9,6,3,1]
     * 思路 ： 递归----往最深层次找，先翻转叶子节点
     * 时间复杂度 ： O(n)
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

    /**
     * 对称二叉树 ： 给你一个二 叉树的根节点 root ， 检查它是否轴对称。
     * 输入：root = [1,2,2,3,4,4,3]
     * 输出：true
     * 思路 ： 递归   ---->   同步移动 p,q 两个指针，p 向左走，q 向右走，若 p,q 所代表节点的数据域相同则证明是镜像的
     * 时间复杂度 ： O(n)
     * */
    public boolean isSymmetric(TreeNode root) {
        return check(root.left, root.right);
    }
    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;   // 上一步已经校验过两个指针都为空的情况了
        if (p.val != q.val) return false;
        return check(p.left, q.right) && check(p.right, q.left) && p.val == q.val;
    }

    /**
     * 二 叉树层序遍历 ： 给你二 叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
     * 输入：root = [3,9,20,null,null,15,7]
     * 输出：[[3],[9,20],[15,7]]
     * 思路 ： 广度优先搜索  --->   根节点入队。队列不空根节点出队，并将所有孩子节点入队列
     */

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);  // 根节点入队列
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
            ans.add(level);
        }
        return ans;
    }

    void dfs (TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        dfs(root.right);
    }

    void bfs (TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            // 队列不空，队头出队、所有孩子节点入队列
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

    /**
     * 将有序数组转换为二 叉搜索树 ：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二 叉搜索树。
     * 输入：nums = [-10,-3,0,5,9]
     * 输出：[0,-3,9,-10,null,5]
     * 解释：[0,-10,5,null,-3,null,9]
     * 思路 ： 平衡二 叉树的中序遍历序列是升序排序的， 根节点为中间位置
     * 时间复杂度 ： O(n)
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }
    public TreeNode helper(int[] nums, int left, int right) {
        if (left > right) return null;
        // 总是选择中间左边的节点作为根节点
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid - 1);
        root.right = helper(nums, mid + 1, right);
        return root;
    }

    /**
     *  验证二 叉搜索树 : 给你一个二 叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
     *  输入：root = [2,1,3]
     *  输出：true
     *  思路 ； 递归，二 叉搜索树--> 左子树 < 根节点 < 右子树
     *  时间复杂度 ： O(n)
     */
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    public boolean isValidBST(TreeNode node, long lower, long upper) {
        // 递归终止条件，递归终止条件是当前节点为空，即遍历到叶子节点，返回 true。
        if (node == null) return true;
        // 当前节点的值应该在 (lower, upper) 中间，否则返回 false。
        if (node.val <= lower || node.val >= upper) return false;
        // 递归判断左右子树是否满足二叉搜索树的定义。
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }

    /**
     * 二 叉 搜索树中第 K 小的元素 ： 给定一个 二 叉 搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
     * 输入：root = [3,1,4,null,2], k = 1
     * 输出：1
     * 思路一 ：中序遍历：中序遍历是二 叉搜索树的升序遍历，因此中序遍历的序列是升序的，因此可以找到第 k 小的元素。
     * 思路二 ： 记录子树的节点数
     * 思路三 ： 平衡二 叉搜索树
     */
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        // 中序遍历，找到第k小的数直接break
        while (root != null || !stack.isEmpty()) {
            // 持续搜索最左下角的元素-----> 一定是最小值
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (--k == 0) {
                break;
            }
            root = root.right;
        }
        return root.val;
    }

    /**
     * 二叉树 的右视图 ： 给定一个 二叉树 的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
     * 输入：root = [1,2,3,null,5,null,4]
     * 输出：[1,3,4]
     * 思路 ： 深度优先搜索，每次都向右搜索，右视图为搜索到当前层数的第一个节点
     * 时间复杂度 ：O(n)
     */
    public List<Integer> rightSideView(TreeNode root) {
        Map<Integer, Integer> rightSideView = new HashMap<>();
        Deque<TreeNode> nodeStack = new LinkedList<>();
        Deque<Integer> depthStack = new LinkedList<>();
        nodeStack.push(root);
        depthStack.push(0);
        while (!nodeStack.isEmpty()) {
            TreeNode node = nodeStack.pop();
            int depth = depthStack.pop();
            if (node != null) {
                // 如果不存在对应深度的节点才插入
                if (!rightSideView.containsKey(depth)) {
                    rightSideView.put(depth, node.val);
                }
                // 栈 ‘后进先出’， 先push left 再 push right
                nodeStack.push(node.left);
                nodeStack.push(node.right);
                // 同一层次的节点，深度一样
                depthStack.push(depth + 1);
                depthStack.push(depth + 1);
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int depth = 0; depth <= depthStack.size(); depth++) {
            ans.add(rightSideView.get(depth));
        }
        return ans;
    }

    /**
     *  二叉树 展开为链表 : 给你一棵 二叉树 ，请你展开它，将其从左往右连接为链表，返回根节点。 按照先序遍历的顺序，展开 二叉树 。
     *  输入：root = [1,2,5,3,4,null,6]
     *  输出：[1,null,2,null,3,null,4,null,5,null,6]
     *  思路 ： 先序遍历得到各个节点的访问顺序
     *  时间复杂度 ： O(n)
     */
    public void flatten(TreeNode root) {
        // 保存前序遍历序列的链表
        List<TreeNode> list = new ArrayList<>();
        preorderTraversal(root, list);
        for (int i = 1; i < list.size(); i++) {
            TreeNode prev = list.get(i - 1), curr = list.get(i);
            prev.left = null;
            prev.right = curr;
        }
    }
    public void preorderTraversal(TreeNode root, List<TreeNode> list) {
        if (root != null) {
            list.add(root);
            preorderTraversal(root.left, list);
            preorderTraversal(root.right, list);
        }
    }

    /**
     * 由前序遍历序列和中序遍历序列构造 二叉树
     * 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
     * 输出: [3,9,20,null,null,15,7]
     * 思路 ： 有前序遍历序列定位根节点， 通过根节点定位左右子树，递归求解左右子树最大深度，求出左右子树最大深度之和
     * 时间复杂度 ： O（n）
     */
    private Map<Integer, Integer> indexMap;
    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历序列中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);

        // 先建立根节点
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 得到左右子树中的节点数目
        int size_left_subTree = inorder_root - inorder_left;
        // 递归的构造左子树，并连接到根节点
        // 先序遍历中 从左边界+1 开始的size_left_subTree 个元素就对应了中序遍历中 从左边界 开始到 根节点位置-1 的元素
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subTree, inorder_left, inorder_left + inorder_root - 1);
        // 递归的构造右子树，并连接到根节点
        // 先序遍历中 从右边界-size_left_subTree 开始的size_right_subTree 个元素就对应了中序遍历中 从根节点+1 开始到 右边界 的元素
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subTree + 1, preorder_right, inorder_left + size_left_subTree + 1, inorder_right);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    /**
     * 路径总和 III : 给定一个 二叉树 的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
     * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
     * 输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
     * 输出：3
     * 思路 ： 深度优先搜索
     * 时间复杂度 ： O(n)
     */
    public int pathSum(TreeNode root, long targetSum) {
        if (root == null) return 0;
        // 找出从当前节点开始满足要求的路径和个数, 递归找所有节点符合题目要求的路径起点
        int ret = rootSum(root, targetSum);
        ret += pathSum(root.left, targetSum);
        ret += pathSum(root.right, targetSum);
        return ret;
    }
    // 递归求解以当前节点为起点的子树中，路径和为 targetSum 的路径数目
    public int rootSum(TreeNode root, long targetSum) {
        int ret = 0;
        if (root == null) return 0;
        int val = root.val;
        if (val == targetSum) {
            ret++;
        }
        ret += rootSum(root.left, targetSum - val);
        ret += rootSum(root.right, targetSum - val);
        return ret;
    }
    /**
     * 思路二 ： 记录前缀和
     * 时间复杂度 ： O(n)
     */
    public int pathSum1(TreeNode root, int target) {
        Map<Long, Integer> prefix = new HashMap<>();
        prefix.put(0L, 1);
        return dfs(root, prefix, 0, target);
    }
    public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
        if (root == null) {
            return 0;
        }
        int ret = 0;
        curr += root.val;

        ret = prefix.getOrDefault(curr - targetSum, 0);
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
        ret += dfs(root.left, prefix, curr, targetSum);
        ret += dfs(root.right, prefix, curr, targetSum);
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);
        return ret;
    }

    /**
     * 二 叉树的最近公共祖先 ： 对于树的两个节点 p , q,最近公共祖先表示为一个节点 x ,满足 x 是 p 和 q 的 最近公共祖先 ，且 x 的深度尽可能大
     * 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
     * 输出：3
     * 思路 ： 递归求解
     * 时间复杂度 ： O(n)
     */
    private TreeNode ans;
    public Solution() {
        this.ans = null;
    }
    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean lson = dfs(root.left, p, q);
        boolean rson = dfs(root.right, p, q);
        if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
            ans = root;
        }
        return lson || rson || (root.val == p.val || root.val == q.val);
    }
    public TreeNode lowsetCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.dfs(root, p, q);
        return this.ans;
    }
    /**
     * 二叉树 的直径 ： 给你一棵 二叉树 的根节点，返回该树的 直径 。
     * 二叉树 的直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的 长度 由它们之间边数表示。
     * 输入：root = [1,2,3,4,5]
     * 输出：3
     * 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度
     * 思路 ：
     */
    int ansDiameter;
    public int diameterOfBinaryTree(TreeNode root) {
        ansDiameter = 1;
        depth(root);
        return ansDiameter - 1;
    }
    public int depth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int L = depth(node.left);
        int R = depth(node.right);
        ansDiameter = Math.max(ansDiameter, L + R + 1);
        return Math.max(L, R) + 1;
    }

    /**
     * 搜索旋转排序数组 :
     * @param args
     */

    /**
     * 爬楼梯 ： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     * 输入：n = 2
     * 输出：2
     * 解释：有两种方法可以爬到楼顶。1. 1 阶 + 1 阶  2. 2 阶
     * 思路 ： 动态规划  爬到第 x级台阶的方案书是爬到第 x-1级台阶的方案数加 x-2级台阶的方案数
     * 时间复杂度  ； O(n)
     */
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; i++) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }

    /**
     * 杨辉三角 ： 每个数是他左上方和右上方数之和
     * 输入: numRows = 5
     * 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
     * 思路 ： 动态规划
     * 时间复杂度 ： O(n^2)
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < numRows; ++i) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(ans.get(i - 1).get(j - 1) + ans.get(i - 1).get(j));
                }
            }
            ans.add(row);
        }
        return ans;
    }

    /**
     * 打家劫舍 ： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
     * 影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     * 输入：[1,2,3,1]
     * 输出：4
     * 思路 ： 动态规划----只有一间房  dp = 1；   有两间房 dp = Math.max(nums[1], nums[2])
     * 有 k间房  dp = Math.max(dp[i - 2] + nums[i], dp[i - 1])
     */
    public int rob(int[] nums) {
        if (nums == null) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[] dp = new int[length];
        // 只有一间房
        dp[0] = nums[0];
        // 只有两件房
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            // 要偷第 i间房子，就不能动第 i-1, 故应该是前 i-2的状态
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length - 1];
    }

    /**
     * 完全平方数 ； 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
     * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是
     * 思路 ： 动态规划 ：
     */
    public int numSquares(int n) {
        int[] f = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int minn = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                minn = Math.min(minn, f[i - j * j]);
            }
            f[i] = minn + 1;
        }
        return f[n];
    }

    /**
     * 最大子数组和 ： 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * 子数组是数组中的一个连续部分。
     * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
     * 输出：6
     * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
     * 思路 ： 动态规划 ：
     */
    public int maxSUbArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }

    /**
     * 合并区间 ： 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
     * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
     * 输出：[[1,6],[8,10],[15,18]]
     * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
     * 思路 ： 排序
     * 时间复杂度 ： O(nlogn)
     */
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }

    /**
     * 轮转数组 : 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
     * 输入: nums = [1,2,3,4,5,6,7], k = 3
     * 输出: [5,6,7,1,2,3,4]
     * 思路 ： 使用额外的数组
     */
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] newArr = new int[n];
        for (int i = 0; i < n; i++) {
            newArr[(i + k) % n] = nums[i];
        }
        System.arraycopy(newArr, 0, nums, 0, n);
    }

    /**
     * 除自身以外数组的乘积 ： 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
     * 思路 ： 创建两个长度为length 的L 和 R 分别表示nums[i] 左边的乘积，R[i] 表示 nums[i] 右边的乘积。
     */
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] answer = new int[length];
        int[] L  = new int[length];
        int[] R = new int[length];
        // 索引0左边的成绩为1
        L[0] = 1;
        for (int i = 1; i < length; i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }
        R[length - 1] = 1;
        for (int i = length - 2; i > 0; i--) {
            R[i] =  R[i + 1] * nums[i + 1];
        }
        for (int i = 0; i < length; i++) {
            answer[i] = L[i] * R[i];
        }
        return answer;
    }
    // 思路二 先构造左边的乘积。再通过一个变量R动态构造右边的成绩并称answer[i]
    public int[] productExceptSelf1(int[] nums) {
        int length = nums.length;
        int[] answer = new int[length];
        answer[0] = 1;
        for (int i = 1; i < length; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }
        int R = 1;
        for (int i = length - 1; i >= 0; i--) {
            answer[i] = answer[i] * R;
            R *= nums[i];
        }
        return answer;
    }

    /**
     * 矩阵置零 ： 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
     * 思路 ： 创建两个数组，分别表示每一行和每一列是否为0。
     */
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = col[j] = true;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    /**
     * 螺旋矩阵 ： 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
     * 思路 ： 创建两个数组，分别表示每一行和每一列是否为0。
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> order = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int rows = matrix.length, columns = matrix[0].length;
        boolean[][] visited = new boolean[rows][columns];
        int total = rows * columns;
        int row = 0, column = 0;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int directionIndex = 0;
        for (int i = 0; i < total; i++) {
            order.add(matrix[row][column]);
            visited[row][column] = true;
            int nextRow = row + directions[directionIndex][0],
                    nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        return order;

    }

    /**
     * 只出现一次的数字 ： 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
     * 思路 ： 任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。
     * 任何数和其自身做异或运算，结果是 0，即 a⊕a=0。
     * 异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
     */
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }

    /**
     * 多数元素 ： 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
     * 思路 ： 排序，众数一定是中间那个。
     */
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    /**
     * 买卖股票的最佳时机 ： 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
     * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
     * 思路 ：记录最低价， 每天考虑我今天出售能否获得最大利润
     */
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int minPrice = Integer.MAX_VALUE;
        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;
            } else if (price - minPrice > maxProfit) {
                maxProfit = price - minPrice;
            }
        }
        return maxProfit;
    }

    /**
     * 旋转图像 ： 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
     * 思路： 第一行旋转后在最后一列，以此类推
     */
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] ans = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans[j][n - i - 1] = matrix[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = ans[i][j];
            }
        }
    }

    /**
     * 搜索二维矩阵 II ： 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
     * 每行的元素从左到右升序排列。
     * 每列的元素从上到下升序排列。
     * 思路 ： 二分查找，从右上角开始，如果当前值大于目标值，则向左移动，如果当前值小于目标值，则向下移动。
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            if (search(row, target) >= 0) {
                return true;
            }
        }
        return false;
    }
    public int search(int[] nums, int target) {
        int low = 0, height = nums.length - 1;
        while (low <= height) {
            int mid = (height - low) / 2 + low;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                height = mid - 1;
            } else if (nums[mid] < target) {
                low = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 搜索插入位置 ： 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     * 思路 ： 二分查找，如果当前值大于目标值，则向左移动，如果当前值小于目标值，则向下移动。
     */
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    /**
     * 搜索二维有序矩阵
     * 思路 ： 一次二分查找， 将m * n 行数据映射到二维数组
     */
    public boolean searchMatrix1(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = m * n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int midValue = matrix[mid / n][mid % n];
            if (midValue < target) {
                left = mid + 1;
            } else if (midValue > target) {
                right = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }

    /**
     * 在排序数组中查找元素的第一个和最后一个位置 ： 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
     * 思路 ： 二分查找
     */
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        }
        return new int[]{-1,-1};
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    /**
     * 搜索旋转排序数组 ：
     * 思路 ： 二分查找
     */
    public int searchRotateArray(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return -1;
        if (n == 1) return nums[0] == target ? 0 : -1;
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // 如果左边的表有序
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }

    /**
     * 寻找旋转排序数组中的最小值
     * 思路 ： 二分查找
     */
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) {
                high = pivot;
            } else {
                low = pivot + 1;
            }
        }
        return nums[low];
    }


    /**
     * 有效的括号 ： 括号匹配为题
     * 思路 ： 栈， 从前往后扫描字符串， 遇到左括号就进栈，遇到右括号就出栈进行匹配
     */
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Map<Character, Character> pairs = new HashMap<>() {{
            put(')', '(');
            put('}', '{');
            put(']', '[');
        }};
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (!pairs.containsKey(ch)) {
                // 遇到左括号进栈
                stack.push(ch);
            } else {
                if (stack.isEmpty() && stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            }
        }
        return stack.isEmpty();
    }

    /**
     * 最小栈
     */
    class MinStack {
        Deque<Integer> xStack;
        Deque<Integer> minStack;

        public MinStack() {
            xStack = new LinkedList<>();
            minStack = new LinkedList<>();
            minStack.push(Integer.MAX_VALUE);
        }

        public void push(int val) {
            xStack.push(val);
            minStack.push(Math.min(minStack.peek(), val));
        }

        public void pop() {
            xStack.pop();
            minStack.pop();
        }

        public int top() {
            return xStack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }

    /**
     *  字符串解码 ：
     *  输入：s = "3[a]2[bc]"
     * 输出："aaabcbc"
     */

    /**
     * 每日温度
     */
    public int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        int[] ans = new int[length];
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < length; i++) {
            int temperature = temperatures[i];
            while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
                int prevIndex = stack.pop();
                ans[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }
        return ans;
    }


    /**
     * 寻找数组中两个数的和等于目标值的索引
     * 使用哈希表存储已遍历的数字及其索引，实现一次遍历找到结果
     * 时间复杂度：O(n)，空间复杂度：O(n)
     *
     * @param nums 整数数组
     * @param target 目标和值
     * @return 包含两个索引的数组，使得这两个索引对应的数字之和等于目标值；
     *         如果没有找到符合条件的两个数，则返回空数组
     */
    public int[] twoSum2(int[] nums, int target) {
        // 使用哈希表存储数字和其索引的映射关系
        Map<Integer, Integer> map = new HashMap<>();

        // 遍历数组，对每个元素检查是否存在匹配的另一个数
        for (int i = 0; i < nums.length; i++) {
            // 如果哈希表中存在目标值与当前数字的差值，说明找到了两个数
            if(map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            // 将当前数字和索引存入哈希表
            map.put(nums[i], i);
        }

        // 没有找到符合条件的两个数，返回空数组
        return new int[0];
    }

    /**
     * 将字符串数组中的字母异位词分组
     * 字母异位词是由相同字母重新排列组成的不同单词
     *
     * @param strs 输入的字符串数组
     * @return 包含字母异位词分组的列表，每个分组包含所有互为字母异位词的字符串
     */
    public List<List<String>> groupAnagrams2(String[] strs) {
        // 创建一个HashMap，用于存储字母异位词分组列表
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            // 统计当前字符串中每个字母的出现次数
            int[] count = new int[26];
            int len = str.length();
            for (int i = 0; i < len; i++) {
                count[str.charAt(i) - 'a']++;
            }
            // 根据字母出现次数构建唯一标识符作为分组key
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (count[i] != 0) {
                    sb.append((char)'a' + i);   // 添加字母
                    sb.append(count[i]);        // 添加出现次数
                }
            }
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }

    /**
     * 找到数组中数字连续序列的最长长度
     *
     * 算法思路：
     * 1. 将所有数字放入HashSet中，实现去重和快速查找
     * 2. 遍历HashSet中的每个数字，如果该数字没有前驱数字(num-1不存在)，
     *    则说明这是一个连续序列的起点
     * 3. 从起点开始向后查找连续的数字，统计当前序列的长度
     * 4. 记录并更新最长序列长度
     *
     * @param nums 输入的整数数组
     * @return 数组中连续序列的最长长度
     */
    public int longestConsecutive2(int[] nums) {
        // 将数组元素存入HashSet，用于去重和O(1)时间复杂度的查找
        Set<Integer> num_set = new HashSet<>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        // 遍历HashSet中的每个数字
        for (int num : num_set) {
            // 只有当当前数字没有前驱数字时，才作为连续序列的起点进行查找
            if(!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                // 从当前数字开始，向后查找连续的数字
                while(num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak ++;
                }

                // 更新最长连续序列长度
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        return longestStreak;
    }

    // 双指针

    /**
     * 将数组中的所有0移动到数组末尾，同时保持非零元素的相对顺序
     * 使用双指针法原地修改数组
     *
     * @param nums 输入的整数数组
     */
    public void moveZeroes1(int[] nums) {
        if (nums.length == 0) {
            return;
        }
        int j = 0;
        // 使用双指针遍历数组，将非零元素依次移到数组前部
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                // 交换非零元素到前面的位置
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j++] = temp;
            }
        }
    }

    /**
     * 计算容器能盛最多水的面积
     * 使用双指针法从数组两端向中间移动，每次移动较矮的一边
     * 时间复杂度：O(n)，空间复杂度：O(1)
     *
     * @param height 整数数组，表示每个位置的高度
     * @return 返回能盛最多水的面积
     */
    public int maxArea1(int[] height) {
        int left = 0, right = height.length - 1, ans = 0;
        // 双指针向中间移动，直到相遇
        while (left < right) {
            // 比较左右两边高度，移动较矮的一边，并计算当前面积
            ans = height[left] < height[right] ?
                    Math.max(ans, (right - left) * height[left++]) :
                    Math.max(ans, (right - left) * height[right--]);
        }
        return ans;
    }

    /**
     * 寻找数组中所有和为0的不重复三元组
     * @param nums 输入的整数数组
     * @return 所有和为0的不重复三元组列表
     */
    public List<List<Integer>> threeSum1(int[] nums) {
        // 排序数组，减少对比次数
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        // 固定第一个数，用双指针寻找另外两个数
        for (int k = 0; k < nums.length; k++) {
            // k是最小值，如果最小值都大于零，那么一定不存在满足条件的三元组
            if (nums[k] > 0) break;
            // 跳过重复元素，避免出现重复的三元组
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            // 双指针分别指向剩余元素的开始和结束位置
            int i = k + 1, j = nums.length - 1;
            while (i < j) {
                int sum = nums[k] + nums[i] + nums[j];
                if (sum < 0) {
                    // 和小于0，需要增大sum值，移动左指针
                    while (i < j && nums[i] == nums[++i]);  // 跳过重复元素向后移动指针
                }else if (sum > 0) {
                    // 和大于0，需要减小sum值，移动右指针
                    while (i < j && nums[j] == nums[--j]);
                }else {
                    // 找到和为0的三元组，添加到结果中
                    ans.add(Arrays.asList(nums[k], nums[i], nums[j]));
                    // 跳过重复元素
                    while (i < j & nums[i] == nums[++i]);
                    while (i < j && nums[j] == nums[--j]);
                }
            }
        }
        return ans;
    }

    /**
     * 计算雨水收集问题的解法三
     * 使用动态规划预处理每个位置左侧和右侧的最大高度，然后计算每个位置能存储的雨水量
     * @param height 表示每个位置高度的整数数组
     * @return 返回能够收集的雨水总量
     */
    public int trap3(int[] height) {
        int ans = 0;
        int n = height.length;
        if (n == 0) {
            return 0;
        }
        // 预处理每个位置左侧的最大高度
        int[] left_max = new int[n];
        left_max[0] = height[0];
        // 遍历数组，更新 left_max 数组为当前元素和左侧最大高度的较大值
        for (int i = 1; i < n; i++)  {
            left_max[i] = Math.max(left_max[i - 1], height[i]);
        }
        // 预处理每个位置右侧的最大高度
        int[] right_max = new int[n];
        right_max[n - 1] = height[n - 1];
        // 遍历数组，更新 right_max 数组为当前元素和右侧最大高度的较大值
        for (int i = n - 2; i >=0; i--) {
            right_max[i] = Math.max(right_max[i + 1], height[i]);
        }
        // 计算每个位置能够存储的雨水量并累加
        for (int i = 0; i < n; i++) {
            ans += Math.min(left_max[i], right_max[i]) - height[i];
        }
        return ans;
    }

    /**
     * 使用单调栈方法计算可以接住的雨水总量
     * 该方法通过维护一个单调递减的栈来寻找每个位置能够形成的凹槽区域
     * 当遇到比栈顶元素高的位置时，计算该凹槽能够存储的雨水量
     *
     * @param height 表示柱子高度的数组，每个元素代表对应位置柱子的高度
     * @return 返回能够接住的雨水总量
     */
    public int trap5(int[] height) {
        int ans = 0;
        Deque<Integer> stack = new LinkedList<>();
        int n = height.length;
        for (int i = 0; i < n; i++) {
            // 当前位置能够与栈中元素形成凹槽来存储雨水
            // 持续弹出栈中比当前位置矮的元素，计算对应的雨水存储量
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();
                int currWidth = i - left - 1;
                int currHeight = Math.min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stack.push(i);
        }
        return ans;
    }

    /**
     * 计算数组中能够接住的雨水总量
     * 使用双指针法从两端向中间遍历，维护左右两侧的最大高度
     * 时间复杂度：O(n)，空间复杂度：O(1)
     *
     * @param height 表示柱子高度的数组，每个元素代表该位置柱子的高度
     * @return 返回能够接住的雨水总量
     */
    public int trap7(int[] height) {
        int ans = 0;
        int n = height.length;
        int left = 0, right = n - 1;
        int leftMax = 0, rightMax = 0;

        // 双指针从两端向中间移动，计算每个位置能接住的雨水
        while (left < right) {
            // 更新左侧最大高度和右侧最大高度
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);

            // 根据较矮的一侧来计算当前位置的雨水量
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }

    /**
     * 计算字符串中最长无重复字符子串的长度
     * 使用滑动窗口算法，通过HashSet记录当前窗口中的字符
     *
     * @param str 输入的字符串
     * @return 返回最长无重复字符子串的长度
     */
    public int lengthOfLongestSubstring1(String str) {
        int ans = 0;
        Set<Character> set = new HashSet<>();
        int n = str.length(), rk = -1;

        // 遍历字符串，i为滑动窗口的左边界
        for (int i = 0; i < n; i++) {
            // 当左边界右移时，从集合中移除前一个字符
            if (i != 0) {
                set.remove(str.charAt(i - 1));
            }

            // 扩展滑动窗口的右边界，直到遇到重复字符
            while (rk + 1 < n && !set.contains(str.charAt(rk + 1))) {
                set.add(str.charAt(rk + 1));
                ++rk;
            }

            // 更新最长子串长度
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }

    /**
     * 查找字符串中所有字母异位词的起始位置
     * 字母异位词是指由相同字母重新排列形成的字符串
     *
     * @param str 待搜索的字符串
     * @param p   目标模式字符串
     * @return 包含所有匹配位置索引的列表
     */
    public List<Integer> findAnagrams1(String str, String p) {
        List<Integer> ans = new ArrayList<>();
        int strLen = str.length(), pLen = p.length();
        if (strLen < pLen) {
            return ans;
        }
        // 使用滑动窗口统计字符频次
        int[] strCount = new int[26];
        int[] pCount = new int[26];
        // 初始化窗口，统计前pLen个字符的频次
        for (int i = 0; i < pLen; i++) {
            ++strCount[str.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }
        // 比较初始窗口是否匹配
        if (Arrays.equals(strCount, pCount)) {
            ans.add(0);
        }
        // 滑动窗口，逐个检查每个可能的位置
        for (int i = 0; i < strLen - pLen; ++i) {
            --strCount[str.charAt(i) - 'a'];
            ++strCount[str.charAt(i + pLen) - 'a'];
            if (Arrays.equals(strCount, pCount)) {
                ans.add(i + 1);
            }

        }

        return ans;
    }

    /**
     * 计算数组中和为k的连续子数组的个数
     *
     * @param nums 输入的整数数组
     * @param k 目标和值
     * @return 返回数组中所有连续子数组和等于k的个数
     */
    public int subarraySum2(int[] nums, int k) {
        int ans = 0;
        // 外层循环遍历所有可能的子数组起始位置
        for (int start = 0; start < nums.length; ++start) {
            int sum = 0;
            // 内层循环从当前起始位置向前累加，计算以start为结束位置的所有子数组和
            for (int end = start; end >= 0; --end) {
                sum += nums[end];
                if (sum == k) {
                    ans++;
                }
            }
        }
        return ans;
    }

    /**
     * 计算数组中和为k的连续子数组的个数
     * 使用前缀和+哈希表的方法优化时间复杂度
     *
     * @param nums 输入的整数数组
     * @param k 目标和值
     * @return 返回和为k的连续子数组的个数
     */
    public int subarraySum3(int[] nums, int k) {
        int ans = 0, pre = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        // 初始化哈希表，前缀和为0的情况出现1次
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            // 计算当前位置的前缀和
            pre += nums[i];
            // 如果存在前缀和为(pre-k)的情况，说明存在子数组和为k
            if (map.containsKey(pre - k)) {
                ans += map.get(pre - k);
            }
            // 更新当前前缀和的出现次数
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return ans;
    }

    /**
     * 计算滑动窗口中的最大值
     * 使用优先队列（最大堆）来维护窗口中的元素，队列中存储元素值和对应的索引
     *
     * @param nums 输入的整数数组
     * @param k 滑动窗口的大小
     * @return 每个滑动窗口中的最大值组成的数组
     */
    public int[] maxSlidingWindow1(int[] nums, int k) {
        int n = nums.length;
        // 创建优先队列，按照元素值降序排列，值相同时按照索引降序排列
        PriorityQueue<int[]> queue = new PriorityQueue<>((pair1, pair2) -> pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1]);
        // 将前k个元素加入优先队列
        for (int i = 0; i < k; i++) {
            queue.offer(new int[]{nums[i], i});
        }
        // 存储结果的数组
        int[] ans = new int[n - k + 1];
        assert queue.peek() != null;
        ans[0] = queue.peek()[0];
        // 处理后续元素，维护滑动窗口
        for (int i = k; i < n; i++) {
            queue.offer(new int[]{nums[i], i});
            // 移除超出窗口范围的元素
            while (true) {
                assert queue.peek() != null;
                if (!(queue.peek()[1] <= i - k)) break;
                queue.poll();
            }
            ans[i - k + 1] = queue.peek()[0];
         }
        return ans;
    }

    /**
     * 使用单调双端队列解决滑动窗口最大值问题
     * 该方法通过维护一个单调递减的双端队列来高效地找到每个滑动窗口中的最大值
     *
     * @param nums 输入的整数数组
     * @param k 滑动窗口的大小
     * @return 包含每个滑动窗口最大值的数组
     */
    public int[] maxSlidingWindow2(int[] nums, int k) {
        int n = nums.length;
        // 使用双端队列存储数组元素的索引，保持队列中对应的值单调递减
        Deque<Integer> deque = new LinkedList<>();

        // 初始化第一个窗口，构建单调递减队列
        for (int i = 0; i < k; i++) {
            // 当前元素大于等于队尾元素时，移除队尾元素以维持单调性
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }

        int[] ans = new int[n - k + 1];
        // 第一个窗口的最大值即为队首索引对应的元素值
        ans[0] = nums[deque.peekFirst()];

        // 处理后续窗口
        for (int i = k; i < n; i++) {
            // 维护队列的单调性：当前元素大于等于队首元素时，清空队列
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekFirst()]) {
                deque.pollLast();
            }
            // 将当前元素索引加入队列尾部
            deque.offerLast(i);

            // 移除超出窗口范围的元素索引
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }

            // 当前窗口的最大值为队首索引对应的元素值
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }

        /**
     * 计算滑动窗口的最大值
     * 使用分块预处理的方法，将数组分成大小为k的块，预计算每块的前缀最大值和后缀最大值
     * 时间复杂度O(n)，空间复杂度O(n)
     *
     * @param nums 输入的整数数组
     * @param k 滑动窗口的大小
     * @return 每个滑动窗口中的最大值组成的数组
     */
    public int[] maxSlidingWindow4(int[] nums, int k) {
        int n = nums.length;
        int[] prefixMax = new int[n];
        int[] suffixMax = new int[n];

        // 预处理：计算每个位置到其所在块起始位置的前缀最大值
        for (int i = 0; i < n; ++i) {
            if (i % k ==0) {
                prefixMax[i] = nums[i];
            } else {
                prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
            }
        }

        // 预处理：计算每个位置到其所在块结束位置的后缀最大值
        for (int i = n - 1; i >= 0; --i) {
            if (i == n - 1 || (i + 1) % k ==0) {
                suffixMax[i] = nums[i];
            } else {
                suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
            }
        }

        // 计算每个滑动窗口的最大值
        int[] ans = new int[n - k + 1];
        for (int i = 0; i < n - k + 1; ++i) {
            ans[i] = Math.max(suffixMax[i], prefixMax[i + k - 1]);
        }
        return ans;
    }

    /**
     * 找到数组中连续子数组的最大和（最大子数组和问题）
     * 使用动态规划思想，维护当前子数组的最大和
     *
     * @param nums 输入的整数数组
     * @return 连续子数组的最大和
     */
    public int maxSubArray(int[] nums) {
        // 初始化前一个位置的最大和为0，答案初始化为数组第一个元素
        int pre = 0, ans = nums[0];

        // 遍历数组，动态更新当前位置的最大子数组和
        for (int x : nums) {
            pre = Math.max(pre, pre + x);
            ans = Math.max(ans, pre);
        }
        return ans;
    }

    /**
     * 合并重叠的区间
     *
     * @param intervals 包含多个区间的二维数组，每个区间包含两个元素[起始位置, 结束位置]
     * @return 合并后的不重叠区间数组
     */
    public int[][] merge1(int[][] intervals) {
        // 处理空数组情况
        if (intervals.length == 0) {
            return new int[0][2];
        }

        // 按照区间起始位置进行排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        // 存储合并后的区间结果
        List<int[]> ans = new ArrayList<>();

        // 遍历所有区间，进行合并操作
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            // 如果结果列表为空，或者当前区间与上一个合并区间不重叠，则直接添加新区间
            if (ans.size() == 0 || ans.get(ans.size() - 1)[1] < L) {
                ans.add(new int[]{L, R});
            } else {
                // 如果当前区间与上一个合并区间重叠，则更新上一个区间的结束位置
                ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], R);
            }
        }

        // 将结果列表转换为数组并返回
        return ans.toArray(new int[ans.size()][]);
    }


    /**
     * 将数组中的元素向右轮转 k 个位置
     * 使用环状替换算法实现数组旋转
     *
     * @param nums 待旋转的整数数组
     * @param k 轮转的步数，向右轮转
     */
    public void rorate1(int[] nums, int k) {
        int n = nums.length;
        // 获取轮转的步数，如果步数大于数组长度，则取步数对数组长度取余
        k = k % n;
        // 计算需要进行多少个独立的环状替换
        int count = gcd(k, n);

        // 对每个环状序列进行元素替换
        for (int start = 0; start < count; ++start) {
            int current = start;
            int prev = nums[start];

            // 在当前环状序列中进行元素轮转替换
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
            } while (start != current);
        }
    }

    /**
     * 计算两个整数的最大公约数
     * 使用欧几里得算法（辗转相除法）递归实现
     *
     * @param x 第一个整数
     * @param y 第二个整数
     * @return x和y的最大公约数
     */
    public int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }

    /**
     * 计算数组中除当前元素外其他所有元素的乘积
     * 对于输入数组中的每个元素，计算除了该元素自身以外其他所有元素的乘积
     *
     * @param nums 输入的整数数组
     * @return 返回一个数组，其中每个位置的值为原数组除该位置元素外其他元素的乘积
     */
    public int[] productExceptSelf2(int[] nums) {
        int length = nums.length;
        // 创建左乘积数组，L[i]表示索引i左侧所有元素的乘积
        int[] L = new int[length];
        // 创建右乘积数组，R[i]表示索引i右侧所有元素的乘积
        int[] R = new int[length];

        int[] ans = new int[length];
        // 初始化边界条件
        L[0] = 1;
        // 计算每个位置左侧所有元素的乘积
        for (int i = 1; i < length; i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }
        // 初始化右乘积数组的边界条件
        R[length - 1] = 1;
        // 计算每个位置右侧所有元素的乘积
        for (int i = length - 2; i >= 0; i--) {
            R[i] = nums[i + 1] * R[i + 1];
        }
        // 将左侧乘积与右侧乘积相乘，得到最终结果
        for (int i = 0; i < length; i++) {
            ans[i] = L[i] * R[i];
        }
        return ans;
    }


    /**
     * 寻找数组中两个数的和等于目标值的索引
     *
     * @param nums 整数数组
     * @param target 目标和值
     * @return 包含两个索引的数组，使得这两个索引对应的数组元素之和等于目标值；
     *         如果没有找到符合条件的两个数，则返回空数组
     */
    public int[] twoSum(int[] nums, int target) {
        // 使用哈希表存储已遍历过的数字及其索引，实现一次遍历查找
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // 检查目标值与当前数字的差值是否已在哈希表中存在
            if (map.containsKey(target - nums[i])) {
                // 找到符合条件的两个数，返回它们的索引
                return new int[]{map.get(target - nums[i]), i};
            }
            // 将当前数字和其索引存入哈希表
            map.put(nums[i], i);
        }
        // 未找到符合条件的两个数，返回空数组
        return new int[0];
    }

    /**
     * 将字符串数组中的字母异位词分组
     * 字母异位词是由重新排列源单词的所有字母得到的新单词
     *
     * @param strs 输入的字符串数组
     * @return 包含字母异位词分组的列表，每个分组包含互为字母异位词的字符串
     */
    public List<List<String>> groupAnagrams1(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            // 统计每个字符出现的次数
            int[] counts = new int[26];
            int len = str.length();
            for (int i = 0; i < len; i++) {
                counts[str.charAt(i) - 'a']++;
            }

            // 根据字符统计数组生成唯一的键值
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    sb.append((char)'a' + i);
                    sb.append(counts[i]);
                }
            }
            String key = sb.toString();

            // 将字符串添加到对应分组中
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }

    /**
     * 将字符串数组中的字母异位词分组
     * 字母异位词是由重新排列源单词所有字母得到的新单词
     *
     * @param strs 输入的字符串数组
     * @return 包含字母异位词分组的列表
     */
    public List<List<String>> groupAnagrams11(String[] strs) {
        // 使用哈希表存储分组结果，键为排序后的字符串，值为异位词列表
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            // 将字符串转换为字符数组并排序，作为分组的键
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);

            // 获取或创建对应的字符串列表，并添加当前字符串
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(str);
            map.put(key, list);
        }
        // 返回所有分组的列表
        return new ArrayList<List<String>>(map.values());
    }

    /**
     * 找到数组中数字组成的最长连续序列的长度
     *
     * @param nums 输入的整数数组
     * @return 最长连续序列的长度
     */
    public int longestSubstring(int[] nums) {
        // 使用HashSet存储所有数字，便于快速查找
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int longestStreak = 0;

        // 遍历集合中的每个数字
        for (int num : set) {
            // 只有当当前数字是连续序列的起始数字时才开始计算（即不存在num-1）
            if (!set.contains(num - 1)) {
                int currentStreak = 1;
                int currentNum = num;

                // 向上查找连续的数字
                while (set.contains(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }
                // 更新最长连续序列长度
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        return longestStreak;
    }

    /**
     * 将数组中的所有0移动到数组末尾，同时保持非零元素的相对顺序
     * 使用双指针技术实现原地移动，时间复杂度为O(n)，空间复杂度为O(1)
     *
     * @param nums 待处理的整数数组，处理后所有0将被移动到数组末尾
     */
    public void moveZeros(int[] nums) {
        if (nums.length == 0) {
            return;
        }
        int i = 0;
        // 使用双指针遍历数组，j为快指针寻找非零元素，i为慢指针指向下一个非零元素应放置的位置
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] != 0) {
                // 将非零元素与当前i位置的元素交换，然后i指针前移
                int temp = nums[i];
                nums[i++] = nums[j];
                nums[j] = temp;
            }
        }
    }

    /**
     * 计算容器能够容纳的最大水量
     * 使用双指针法从数组两端向中间移动，每次移动较矮的那根柱子的指针
     * 时间复杂度：O(n)，空间复杂度：O(1)
     *
     * @param height 整数数组，表示每根柱子的高度
     * @return 返回能容纳的最大水量
     */
    public int maxArea2(int[] height) {
        int left = 0, right = height.length - 1, ans = 0;
        // 双指针向中间移动，直到相遇
        while (left < right) {
            // 比较左右两边高度，移动较矮的一边指针，并计算当前面积
            ans = height[left] < height[right] ?
                    Math.max(ans, (right - left) * height[left++]) :
                    Math.max(ans, (right - left) * height[right--]);
        }
        return ans;
    }

    /**
     * 寻找数组中所有和为0的三元组
     *
     * @param nums 输入的整数数组
     * @return 所有不重复的三元组列表，每个三元组的和为0
     */
    public List<List<Integer>> threeSum2(int[] nums) {
        // 先对数组进行排序，为双指针法做准备
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();

        // 遍历数组，固定第一个元素
        for (int first = 0; first < nums.length; first++) {
            // 跳过重复的第一个元素，避免产生重复的三元组
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }

            // 使用双指针法寻找剩余两个元素
            int second = first + 1, third = nums.length - 1;
            // 目标值为第一个元素的相反数，这样三个数相加等于0
            int target = -nums[first];

            // 双指针向中间移动寻找符合条件的组合
            while (second < third) {
                int sum = nums[second] + nums[third];
                if (sum == target) {
                    // 找到符合条件的三元组，添加到结果中
                    ans.add(Arrays.asList(nums[first], nums[second], nums[third]));
                    second++;
                    third--;

                    // 跳过重复的第二个元素
                    while (second < third && nums[second] == nums[second - 1]) {
                        second++;
                    }

                    // 跳过重复的第三个元素
                    while (second < third && nums[third] == nums[third + 1]) {
                        third--;
                    }
                } else if (sum < target) {
                    // 和小于目标值，移动左指针增大和
                    second++;
                } else {
                    // 和大于目标值，移动右指针减小和
                    third--;
                }
            }
        }
        return ans;
    }


    /**
     * 计算字符串中最长无重复字符子串的长度
     * 使用滑动窗口算法，通过HashSet记录当前窗口中的字符
     *
     * @param str 输入的字符串
     * @return 返回最长无重复字符子串的长度
     */
    public int lengthOfLongestSubstring2(String str) {
        int ans = 0;
        Set<Character> set = new HashSet<>();
        int len = str.length(), right = -1;

        // 滑动窗口的左指针遍历整个字符串
        for (int left = 0; left < len; left++) {
            // 当左指针向右移动时，将前一个字符从集合中移除
            if (left != 0) {
                set.remove(str.charAt(left - 1));
            }

            // 扩展右边界，直到遇到重复字符为止
            while (right + 1 < len && !set.contains(str.charAt(right + 1))) {
                set.add(str.charAt(right + 1));
                ++right;
            }

            // 更新最大长度结果
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    /**
     * 查找字符串s中所有与字符串p互为字母异位词的子串的起始索引
     * 字母异位词是指由相同字母重新排列形成的字符串
     *
     * @param s 待搜索的字符串
     * @param p 用于匹配的模式字符串
     * @return 包含所有匹配子串起始索引的列表
     */
    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int sLen = s.length(), pLen = p.length();
        // 如果s的长度小于p，直接返回空结果
        if (sLen < pLen) {
            return ans;
        }
        // 使用数组统计字符频次，sCount统计滑动窗口中字符频次，pCount统计模式串字符频次
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        // 初始化：统计第一个窗口和模式串的字符频次
        for (int i = 0; i < pLen; i++) {
            sCount[s.charAt(i) - 'a']++;
            pCount[p.charAt(i) - 'a']++;
        }
        // 检查初始窗口是否匹配
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }
        // 滑动窗口：逐个移动窗口并检查是否匹配
        for (int i = 0; i < sLen - pLen; i++) {
            --sCount[s.charAt(i) - 'a'];
            sCount[s.charAt(i + pLen) - 'a']++;
            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }
        return ans;
    }

    /**
     * 计算数组中和为k的连续子数组的个数
     * 使用前缀和+哈希表的方法优化时间复杂度
     *
     * @param nums 输入的整数数组
     * @param k 目标和值
     * @return 和为k的连续子数组的个数
     */
    public int subArraySum(int[] nums, int k) {
        int ans = 0, pre = 0;
        // 哈希表存储前缀和及其出现次数，初始化前缀和为0的情况出现1次
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        // 遍历数组，计算前缀和并统计满足条件的子数组个数
        for (int num : nums) {
            pre += num;
            // 如果存在前缀和为(pre-k)的情况，说明找到了和为k的子数组
            if (map.containsKey(pre - k)) {
                ans += map.get(pre - k);
            }
            // 更新当前前缀和的出现次数
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return ans;
    }


    /**
     * 找到数组中连续子数组的最大和（Kadane算法）
     * 状态转移方程: dp[i] = max(dp[i-1] + nums[i], nums[i])
     * 其中dp[i]表示以第i个元素结尾的最大子数组和
     * 时间复杂度：O(n)，其中n是数组长度，只需要遍历数组一次
     * 空间复杂度：O(1)，只使用了常数级别的额外空间
     *
     * @param nums 输入的整数数组
     * @return 连续子数组的最大和
     */
    public int maxSubArray1(int[] nums) {
        int ans = nums[0], pre = 0;
        for (int num : nums) {
            pre = Math.max(pre + num, num);
            ans = Math.max(ans, pre);
        }
        return ans;
    }

    /**
     * 合并重叠区间
     * 算法思路：
     * 1. 首先对区间按照起始位置进行排序，这样可以保证相邻的区间在排序后也是相邻的
     * 2. 遍历排序后的 区间 数组：
     *    - 如果结果列表为空，或者当前区间的起始位置大于结果列表中最后一个区间的结束位置，
     *      说明两个区间不重叠，直接将当前区间添加到结果列表中
     *    - 否则，说明两个区间重叠，需要合并，更新结果列表中最后一个区间的结束位置为两个区间结束位置的最大值
     * 时间复杂度：O(n log n)，其中 n 是区间的数量
     *   - 排序的时间复杂度为 O(n log n)
     *   - 遍历区间的时间复杂度为 O(n)
     *   - 总体时间复杂度为 O(n log n)
     * 空间复杂度：O(log n) 或 O(n)，取决于排序算法的实现
     *   - 排序需要 O(log n) 的栈空间
     *   - 结果数组需要 O(n) 的空间
     *
     * @param intervals 包含多个区间的二维数组，每个区间包含两个元素[起始位置, 结束位置]
     * @return 合并后的不重叠 区间 数组
     */
    public int[][] merge2(int[][] intervals) {
        // 处理空数组的情况
        if (intervals.length == 0) {
            return new int[0][2];
        }
        // 按区间起始位置排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        // 创建结果列表
        List<int[]> ans = new ArrayList<>();
        // 遍历所有区间，进行合并操作
        for (int[] interval : intervals) {
            int L = interval[0], R = interval[1];
            // 如果结果列表为空||当前区间的起始位置大于当前结果列表中的最后一个区间的结束位置，则说明当前区间可以独立合并，将其加入结果列表
            if (ans.isEmpty() || L > ans.getLast()[1]) {
                ans.add(new int[]{L, R});
            } else {
                // 否则，将当前区间与上一个区间进行合并
                ans.getLast()[1] = Math.max(ans.getLast()[1], R);
            }
        }
        // 返回结果列表，将列表转换为数组
        return ans.toArray(new int[ans.size()][]);
    }

    /**
     * 将数组中的元素向右轮转 k 个位置
     *
     * @param nums 待轮转的整数数组
     * @param k 轮转的步数，表示元素向右移动的位置数
     */
    public void rotate1(int[] nums, int k) {
        int n = nums.length;
        // 创建新数组用于存储轮转后的结果
        int[] newArr = new int[n];
        // 遍历原数组，将每个元素放置到轮转后的新位置
        for (int i = 0; i < n; i++) {
            newArr[(i + k) % n] = nums[i];
        }
        // 将新数组的内容复制回原数组
        System.arraycopy(newArr, 0, nums, 0, n);
    }

    /**
     * 计算数组中除自身以外元素的乘积
     * 对于输入数组中的每个元素，计算除了该元素之外其他所有元素的乘积
     *
     * @param nums 输入的整数数组
     * @return 返回一个数组，其中每个位置的值是原数组除该位置外所有元素的乘积
     */
    public int[] productExceptSelf3(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }

        int numsLen = nums.length;
        int[] ans = new int[numsLen];

        // 构建左侧乘积数组到ans中
        ans[0] = 1;
        for (int i = 1; i < numsLen; i++) {
            ans[i] = nums[i - 1] * ans[i - 1];
        }

        // 动态维护右侧乘积并同时更新ans数组
        int rightProduct = 1;
        for (int i = numsLen - 1; i >= 0; i--) {
            ans[i] *= rightProduct;
            rightProduct *= nums[i];
        }

        return ans;
    }

    /**
     * 将矩阵中为0的元素所在的行和列都设置为0
     * 使用原地算法，利用矩阵的第一行和第一列作为标记位来记录需要置0的行列信息
     *
     * @param matrix 输入的二维整数矩阵，处理后该矩阵会被直接修改
     */
    public void setZeroes1(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        boolean row0_flag = false;
        boolean col0_flag = false;

        // 检查第一行是否原本就包含0元素
        for (int j = 0; j < col; j++) {
            if (matrix[0][j] == 0) {
                row0_flag = true;
                break;
            }
        }

        // 检查第一列是否原本就包含0元素
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == 0) {
                col0_flag = true;
                break;
            }
        }

        // 遍历矩阵(除第一行第一列外)，将为0元素的行列信息记录在第一行第一列对应位置
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }

        // 根据第一行第一列的标记信息，将对应行列置0
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // 如果第一行原本有0，则将整行置0
        if (row0_flag) {
            for (int j = 0; j < col; j++) {
                matrix[0][j] = 0;
            }
        }

        // 如果第一列原本有0，则将整列置0
        if (col0_flag) {
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        }
    }

    /**
     * 按照螺旋顺序遍历矩阵，并返回所有元素
     *
     * @param matrix 输入的二维整数矩阵
     * @return 按照螺旋顺序排列的元素列表
     */
    public List<Integer> spiralOrder1(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        // 检查矩阵是否为空
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return ans;
        }

        // 初始化矩阵行数、列数和访问标记数组
        int rows = matrix.length, cols = matrix[0].length;
        boolean [][] visited = new boolean[rows][cols];
        int total = rows * cols;

        // 当前位置和方向数组（右、下、左、上）
        int row = 0, col = 0;
        int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};
        int directionIndex = 0;

        // 按螺旋顺序遍历所有元素
        for (int i = 0; i < total; i++) {
            ans.add(matrix[row][col]);
            visited[row][col] = true;

            // 计算下一个位置
            int nextRow = row + directions[directionIndex][0], nextCol = col + directions[directionIndex][1];

            // 检查是否需要转向（越界或已访问）
            if (nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols || visited[nextRow][nextCol]) {
                directionIndex = (directionIndex + 1) % 4;
            }

            // 更新当前位置
            row += directions[directionIndex][0];
            col += directions[directionIndex][1];
        }
        return ans;
    }

    /**
     * 将二维矩阵顺时针旋转90度
     *
     * 算法思路：
     * 1. 创建一个新的矩阵，将原矩阵的元素按照旋转规律复制到新矩阵中
     * 2. 旋转规律：原矩阵的第row行第col列元素，旋转后位于第col行第(n-row-1)列
     * 3. 将新矩阵的内容复制回原矩阵
     *
     * 示例：
     * 原矩阵：         旋转后：
     * 1  2  3  4      13  9  5  1
     * 5  6  7  8  ->  14  10 6  2
     * 9  10 11 12     15  11 7  3
     * 13 14 15 16     16  12 8  4
     *
     * @param matrix 待旋转的n×n二维矩阵
     */
    public void rotate1(int[][] matrix) {
        /**
         * 1   2   3   4
         * 5   6   7   8
         * 9   10  11  12
         * 13  14  15  16
         *      ||                  matrix[row][col] = matrix[col][n - row - 1]
         * 13   9   5   1
         * 14   10  6   2
         * 15   11  7   3
         * 16   12  8   4
         */
        int row = matrix.length, col = matrix[0].length;
        // 创建新矩阵用于存储旋转后的结果
        int[][] matrixNew = new int[row][col];
        // 按照旋转规律将原矩阵元素复制到新矩阵
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                matrixNew[i][j] = matrix[j][row - i - 1];
            }
        }
        // 将旋转后的结果复制回原矩阵
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                matrix[i][j] = matrixNew[i][j];
            }
        }
    }


    /**
     * 将n×n矩阵顺时针旋转90度
     * 通过循环遍历矩阵的四分之一区域，对每个位置的元素进行四元组循环替换
     *
     * @param matrix n×n的二维整数矩阵，将被原地修改
     */
    /**
     * 将n×n矩阵顺时针旋转90度
     * 通过遍历矩阵四分之一区域，对每个位置的四元组进行循环交换实现原地旋转
     *
     * @param matrix n×n的二维整数矩阵，旋转后结果将直接修改原矩阵
     */
    public void rotate3(int[][] matrix) {
        /**
         *          原矩阵：         旋转后：
         *       1  2  3  4      13  9  5  1
         *       5  6  7  8  ->  14  10 6  2
         *       9  10 11 12     15  11 7  3
         *       13 14 15 16     16  12 8  4
         */
        int n = matrix.length;
        // 遍历矩阵的四分之一区域，进行四元组元素交换
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1)/ 2; ++j) {
                // 四元组循环替换：(i,j) -> (j,n-1-i) -> (n-1-i,n-1-j) -> (n-1-j,i) -> (i,j)
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }

    /**
     * 在二维矩阵中搜索目标值
     * 矩阵每行都是有序的，对每行使用二分搜索查找目标值
     * @param matrix 二维整数矩阵，每行元素按升序排列
     * @param target 要搜索的目标值
     * @return 如果找到目标值返回true，否则返回false
     */
    public boolean searchMatrix2(int[][] matrix, int target) {
        // 遍历矩阵的每一行
        for (int[] row : matrix) {
            // 在当前行中使用二分搜索查找目标值
            int index = binarySearch(row, target);
            if (index >= 0) {
                return true;
            }
        }
        return false;
    }
    int binarySearch(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        // 二分搜索循环
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num >  target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }




    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.subArraySum(new int[]{1,1,1}, 2));
        System.out.println(solution.findAnagrams2("cbaebabacd", "abc"));
        System.out.println("=========================<计算数组中除当前元素外其他所有元素的乘积>==\n");
        System.out.println("数组中除当前元素外其他所有元素的乘积：" + Arrays.toString(solution.productExceptSelf2(new int[]{1,2,3,4,5})));
        System.out.println("=========================<将数组中的元素向右轮转 k 个位置>=========\n");
        solution.rorate1(new int[]{1,2,3,4,5,6,7}, 2);
        System.out.println("==========================<合并重叠区间>=====================\n");
        System.out.println("合并重叠区间：" + Arrays.deepToString(solution.merge1(new int[][]{{1,3},{2,6},{8,10},{15,18}})));
        System.out.println("===========================<最大子数组和>================\n");
        System.out.println("最大子数组和：" + solution.maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
        System.out.println("==========================<滑动窗口最大值>===============\n");
        System.out.println("滑动窗口最大值：" + Arrays.toString(solution.maxSlidingWindow2(new int[]{1,3,-1,-3,5,3,6,7}, 3)));
        System.out.println("滑动窗口最大值：" + Arrays.toString(solution.maxSlidingWindow1(new int[]{1,3,-1,-3,5,3,6,7}, 3)));
        System.out.println("滑动窗口最大值：" + Arrays.toString(solution.maxSlidingWindow4(new int[]{1,3,-1,-3,5,3,6,7}, 3)));
        System.out.println("==========================<和为k的子数组数>==============\n");
        System.out.println("和为k的子数组数：" + solution.subarraySum2(new int[]{1,1,1}, 2));
        System.out.println("和为k的子数组数：" + solution.subarraySum3(new int[]{1,1,1}, 2));
        System.out.println("=========================<两数之和>=====================\n");
        System.out.println("两数之和：" + Arrays.toString(solution.twoSum2(new int[]{2,7,11,15}, 9)));
        System.out.println("=========================<字母异位次分组>=================\n");
        System.out.println("字母异位词排序：" + Collections.singletonList(solution.groupAnagrams2(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"})));
        System.out.println("=========================<最长连续序列>===================\n");
        System.out.println("最长连续序列：" + solution.longestConsecutive(new int[]{100,4,200,1,3,2}));
        System.out.println("=========================<移动零>========================\n");
        solution.moveZeroes1(new int[]{0,1,0,3,12});
        System.out.println("移动零： " );
        System.out.println("==========================<成水最多的容器>=================\n");
        System.out.println("成水最多的容器：" + solution.maxArea1(new int[]{1,8,6,2,5,4,8,3,7}));
        System.out.println("==========================<三数之和>======================\n");
        System.out.println("三数之和：" + solution.threeSum1(new int[]{-1,0,1,2,-1,-4}));

        System.out.println(solution.longestConsecutive(new int[]{1,2,3,4,5,6,7,8,9}));
        System.out.println("=========================<盛水最多的容器>=====================\n");
        int[] arr = new int[]{1,8,6,2,5,4,8,3,7};
        System.out.println("盛水最多的容器答案：" + solution.maxArea(arr) + "/n");

        System.out.println("===========================<接雨水>==========================\n");
        System.out.println("接雨水的答案：" + solution.trap1(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
        System.out.println("接雨水的答案：" + solution.trap2(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
        System.out.println("接雨水的答案：" + solution.trap3(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
        System.out.println("接雨水的答案：" + solution.trap5(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
        System.out.println("接雨水的答案：" + solution.trap7(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));

        System.out.println("===========================<无重复的最长子串>===================\n");
        System.out.println("无重复的最长子串答案：" + solution.lengthOfLongestSubstring1("abcabcbb") + "\n");

        System.out.println("===========================<找到字符串中所有字母异位词>===========\n");
        System.out.println("<找到字符串中所有字母异位词>答案为：" + solution.findAnagrams1("cbaebabacd", "abc") + "\n");
        System.out.println("=======================<无重复字符的最长子串>===================\n");
        System.out.println("无重复字符的最长字串答案：" + solution.lengthOfLongestSubstring("abcabcbb") + "\n");

        System.out.println("===================<找到字符串中所有字母的异位词>=================\n");
        System.out.println("<找到字符串中所有字母的异位词>答案为：" + solution.findAnagrams("cbaebabacd", "abc") + "\n");

        System.out.println("=======================<和为 k 的子数组>=======================\n");
        System.out.println("<和为 k 的子数组>答案为：" + solution.subarraySum1(new int[]{1,2,3}, 3) + "\n");

        System.out.println("=======================<滑动窗口最大值>========================\n");
        System.out.println("<滑动窗口最大值>答案为：" + Arrays.toString(solution.maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)) + "\n");


        Deque<Integer> depthStack = new LinkedList<>();
        depthStack.push(1);
        depthStack.push(2);
        System.out.println(depthStack.size());

    }











    // public static void main(String[] args) {
    //     Scanner scanner = new Scanner(System.in);
    //     int T = scanner.nextInt();
    //     scanner.nextLine();
    //     for (int t = 0; t < T; t++) {
    //         String[] mn = scanner.nextLine().split(" ");
    //         int m = Integer.parseInt(mn[0]);
    //         int n = Integer.parseInt(mn[1]);
    //         String s = scanner.nextLine().trim();
    //         String tStr = scanner.nextLine().trim();
    //
    //         int diff = n - m;
    //         if (diff % 2 != 0) {
    //             System.out.println("NO");
    //             continue;
    //         }
    //         int k = diff / 2;
    //         if (k == 0) {
    //             System.out.println(s.equals(tStr) ? "YES" : "NO");
    //             continue;
    //         }
    //         boolean found = false;
    //         for (int i = 0; i <= m - k; i++) {
    //             String sub = s.substring(i, i + k);
    //             String sNew = s.substring(0, i) + s.substring(i + k);
    //             String tNew = tStr + sub;
    //             if (sNew.equals(tNew)) {
    //                 found = true;
    //                 break;
    //             }
    //         }
    //         System.out.println(found ? "YES" : "NO");
    //     }
    //     scanner.close();
    // }




    // public static void main(String[] args) {
    //     Scanner scanner = new Scanner(System.in);
    //     int T = scanner.nextInt();
    //     scanner.nextLine();
    //
    //     while (T-- > 0) {
    //         int n = scanner.nextInt();
    //         String s = scanner.nextLine().trim();
    //
    //         StringBuilder res = new StringBuilder();
    //         int zeroCount = 0;
    //
    //         for (char c : s.toCharArray()) {
    //             if (c == '0') {
    //                 if (zeroCount > 0) {
    //                     res.append("1".repeat(zeroCount - 1));
    //                     res.append('0');
    //                     zeroCount = 0;
    //                 }
    //                 res.append('1');
    //             } else {
    //                 zeroCount++;
    //             }
    //         }
    //
    //         if (zeroCount > 0) {
    //             res.append("1".repeat(zeroCount - 1));
    //             res.append('0');
    //         }
    //
    //         System.out.println(res.toString());
    //     }
    //     scanner.close();
    // }


    // 矿工宝石采集
    // public static void main(String[] args) {
    //     Scanner in = new Scanner(System.in);
    //     // 注意 hasNext 和 hasNextLine 的区别
    //     int n =  in.nextInt();
    //     int m = in.nextInt();
    //     int[] miners = new int[n];
    //     for (int i = 0; i < n; i++) {
    //         miners[i] = in.nextInt();
    //     }
    //     int[] gems = new int[m];
    //     for (int i = 0; i < m; i++) {
    //         gems[i] = in.nextInt();
    //     }
    //
    //     Arrays.sort(miners);
    //     Arrays.sort(gems);
    //
    //     int i = 0;
    //     int j = 0;
    //     int count = 0;
    //     while (i < n && j < m) {
    //         if (miners[i] >= gems[j]) {
    //             count++;
    //             i++;
    //             j++;
    //         } else {
    //             i++;
    //         }
    //     }
    //     System.out.println(count);
    //     in.close();
    // }

    // 宝藏猎人
    // public static void main(String[] args) {
    //     Scanner sc = new Scanner(System.in);
    //     int n = sc.nextInt();
    //     int m = sc.nextInt();
    //     int[] warriors = new int[];
    //     for (int i = 0; i < n; i++) {
    //         warriors[i] = sc.nextInt();
    //     }
    //
    //     int[] boxes = new int[m];
    //     for (int i = 0; i < m; i++) {
    //         boxes[i] = sc.nextInt();
    //     }
    //
    //     if (n > m) {
    //         System.out.println("No");
    //         return;
    //     }
    //
    //     Arrays.sort(warriors);
    //     Arrays.sort(boxes);
    //
    //     if (warriors[0] < boxes[0]) {
    //         System.out.println("No");
    //         return;
    //     }
    //
    //     if (warriors[n - 1] < boxes[m - 1]) {
    //         System.out.println("No");
    //         return;
    //     }
    //
    //     System.out.println("Yes");
    // }


    // public static void main(String[] args) throws IOException {
    //     Scanner sc = new Scanner(System.in);
    //     BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    //     StringTokenizer st;
    //     final long INF = 100000000000000000L;
    //
    //     while (true) {
    //         st = new StringTokenizer(br.readLine());
    //         int n = Integer.parseInt(st.nextToken());
    //         int m = Integer.parseInt(st.nextToken());
    //         if (n == 0 && m == 0) {
    //             break;
    //         }
    //         List<List<long[]>> graph = new ArrayList<>();
    //         for (int i = 0; i <= n; i++) {
    //             graph.add(new ArrayList<>());
    //         }
    //
    //         for (int i = 0; i < m; i++) {
    //             st = new StringTokenizer(br.readLine());
    //             int xi = Integer.parseInt(st.nextToken());
    //             int yi = Integer.parseInt(st.nextToken());
    //             int hi = Integer.parseInt(st.nextToken());
    //             int ti = Integer.parseInt(st.nextToken());
    //             long h_eff  = (hi == -1) ? INF : hi;
    //             graph.get(xi).add(new long[]{yi, h_eff, ti});
    //             graph.get(yi).add(new long[]{xi, h_eff, ti});
    //         }
    //
    //         st = new StringTokenizer(br.readLine());
    //         int S = Integer.parseInt(st.nextToken());
    //         int T = Integer.parseInt(st.nextToken());
    //         int H = Integer.parseInt(st.nextToken());
    //
    //         long[] dist_minhi = new long[n + 1];
    //         Arrays.fill(dist_minhi, -1);
    //         dist_minhi[S] = INF;
    //         PriorityQueue<long[]> heapMax = new PriorityQueue<>((a, b) -> Long.compare(b[0], a[0]));
    //         heapMax.offer(new long[]{INF, S});
    //
    //         while (!heapMax.isEmpty()) {
    //             long[] current = heapMax.poll();
    //             long min_val = current[0];
    //             int u = (int) current[1];
    //             if (min_val < dist_minhi[u]) continue;
    //             for (long[] edge : graph.get(u)) {
    //                 int v = (int) edge[0];
    //                 long h_eff = edge[1];
    //                 long new_min = Math.min(min_val, h_eff);
    //                 if (new_min > dist_minhi[v]) {
    //                     dist_minhi[v] = new_min;
    //                     heapMax.offer(new long[]{new_min, v});
    //                 }
    //             }
    //         }
    //         long M_max = dist_minhi[T];
    //         if (M_max == -1) {
    //             System.out.println("Impossible!");
    //             continue;
    //         }
    //
    //         long threshold;
    //         long max_final;
    //
    //         if (M_max >= H) {
    //             max_final = H;
    //             threshold = H;
    //         } else {
    //             max_final = M_max;
    //             threshold = M_max;
    //         }
    //
    //         long[] dist_time = new long[n + 1];
    //         Arrays.fill(dist_time, INF);
    //         dist_time[S] = 0;
    //         PriorityQueue<long[]> heapTime = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
    //         heapTime.offer(new long[]{0, S});
    //
    //         while (!heapTime.isEmpty()) {
    //             long[] current = heapTime.poll();
    //             long time_val = current[0];
    //             int u = (int) current[1];
    //
    //             if (time_val > dist_time[u]) continue;
    //             if (u == T) break;
    //
    //             for (long[] edge : graph.get(u)) {
    //                 int v = (int) edge[0];
    //                 long h_eff = edge[1];
    //                 long t = edge[2];
    //                 if (h_eff < threshold) continue;
    //                 long new_time = time_val + t;
    //                 if (new_time < dist_time[v]) {
    //                     dist_time[v] = new_time;
    //                     heapTime.offer(new long[]{new_time, v});
    //                 }
    //             }
    //         }
    //         long min_time = dist_time[T];
    //         if (min_time == INF) {
    //             System.out.println("Impossible!");
    //         } else {
    //             System.out.println(max_final + " " + min_time);
    //         }
    //     }
    // }


    // public static void main(String[] args) throws IOException {
    //     BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    //     String[] firstLine = br.readLine().split(" ");
    //     int n = Integer.parseInt(firstLine[0]);
    //     int k = Integer.parseInt(firstLine[1]);
    //     String[] secondLine = br.readLine().split(" ");
    //     int[] a = new int[n];
    //     for (int i = 0; i < n; i++) {
    //         a[i] = Integer.parseInt(secondLine[i]);
    //     }
    //
    //     if (n == 0) {
    //         System.out.println(0);
    //         return;
    //     }
    //
    //     long[] P = new long[n + 1];
    //     P[0] = 0;
    //     for (int i = 1; i <= n; i++) {
    //         P[i] = P[i - 1] + a[i - 1];
    //     }
    //
    //     int[] Q = new int[n + 1];
    //     for (int i = 0; i <= n; i++) {
    //         if (P[i] % 2 == 0) {
    //             Q[i] = 0;
    //         } else {
    //             Q[i] = 1;
    //         }
    //     }
    //
    //     int maxLen = 0;
    //     int start = 0;
    //
    //     for (int i = 1; i < n; i++) {
    //         if (Math.abs(a[i] - a[i - 1]) > k) {
    //             int end = i - 1;
    //             int segMax = processSegment(start, end,  Q);
    //             maxLen = Math.max(maxLen, segMax);
    //             start = i;
    //         }
    //     }
    //
    //     int segMax = processSegment(start, n - 1, Q);
    //     maxLen = Math.max(maxLen, segMax);
    //     System.out.println(maxLen);
    // }
    //
    // private static int processSegment(int start, int end, int[] Q) {
    //     if (start > end) {
    //         return 0;
    //     }
    //
    //     int segmenMax = 0;
    //     int min0 = -1;
    //     int min1 = -1;
    //
    //     if (Q[start] == 0) {
    //         min0 = start;
    //     } else {
    //         min1 = start;
    //     }
    //
    //     for (int j = start; j <= end; j++) {
    //         if (j > start) {
    //             if (Q[j] == 0) {
    //                 if (min0 == -1) {
    //                     min0 = j;
    //                 }
    //             } else {
    //                 if (min1 == -1) {
    //                     min1 = j;
    //                 }
    //             }
    //         }
    //
    //         int par = Q[j + 1];
    //         if (par == 0 && min0 != -1) {
    //             int len = j - min0 + 1;
    //             if (len > segmenMax) {
    //                 segmenMax = len;
    //             }
    //         } else if (par == 1 && min1 != -1) {
    //             int len = j - min1 + 1;
    //             if (len > segmenMax) {
    //                 segmenMax = len;
    //             }
    //         }
    //     }
    //     return segmenMax;
    // }

}
